package offer;

@FunctionalInterface

public interface IsBalanced {
    /**
     * 判断一个二叉树是否为平衡二叉树
     * @param root
     * @return
     */
    boolean isBalanced(TreeNode root);

}
class IsBalancedImpl1 implements IsBalanced{
    private boolean isBalanced = true;

    @Override
    /**
     *   解题思路：如果树是平衡二叉树，则其左右子树平衡因子之差绝对值小于等于1，递归实现
     */
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }else{
            isBalancedHelper(root,0);
            return isBalanced;
        }
    }
    private int isBalancedHelper(TreeNode root, int height){
        // 当已经确认该树不平衡时，可以剪枝
        if(!isBalanced){
            return -1;
        }
        int leftHeight = height,rightHeight = height;
        if(root.left != null && root.right != null){
            leftHeight = isBalancedHelper(root.left,height + 1);
            rightHeight = isBalancedHelper(root.right,height + 1);
        }else if(root.left == null && root.right == null){
            // do nothing
        }else if(root.left == null){
            rightHeight = isBalancedHelper(root.right,height + 1);
        }else if(root.right == null){
            leftHeight = isBalancedHelper(root.left,height + 1);
        }
        if(Math.abs(leftHeight - rightHeight) > 1){
            isBalanced = false;
        }
        return Math.max(leftHeight,rightHeight);
    }
}
